package heap;

import java.util.Arrays;
import java.util.Comparator;

public class BinaryHeap<E> implements Heap<E> {

	private static final int DEFAULT_CAPACITY = 16;
	
	private int size;
	private E[] elements;
	private Comparator<E> comparator;
	
	
	public BinaryHeap() {
		this(null, null);
	}
	
	public BinaryHeap(Comparator<E> comparator) {
		this(null, comparator);
	}
	
	public BinaryHeap(E[] elements) {
		this(elements, null);
	}
	
	public BinaryHeap(E[] elements, Comparator<E> comparator) {
		this.comparator = comparator;
		if (elements == null || elements.length == 0) {
			this.elements = (E[])new Object[DEFAULT_CAPACITY];
		} else {
			int capacity = Math.max(DEFAULT_CAPACITY, elements.length);
			this.elements = (E[])new Object[capacity];
			for (int i = 0; i < elements.length; i++) {
				this.elements[i] = elements[i];
			}
			size = elements.length;
			heapify();
		}
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public void clear() {
		for (int i = 0; i < size; i++) {
			elements[i] = null;
		}
		size = 0;
	}

	@Override
	public void add(E element) {
		elementNotNullCheck(element);
		ensureCapacity(size + 1);
		elements[size++] = element;
		siftUp(size - 1);
	}


	@Override
	public E get() {
		emptyCheck();
		return elements[0];
	}

	@Override
	public E remove() {
		emptyCheck();
		int lastIndex = --size;
		E root = elements[0];
		elements[0] = elements[lastIndex];
		elements[lastIndex] = null;
		siftDown(0);
		return root;
	}

	@Override
	public E replace(E element) {
		elementNotNullCheck(element);
		E root = null;
		if (size == 0) {
			elements[size++] = element;
		} else {
			root = elements[0];
			elements[0] = element;
			siftDown(0);
		}
		return root;
	}
	
	
	/**
	 * 批量建堆, 采用自下而上的下滤
	 */
 	private void heapify() {
 		for (int i = (size >> 1) - 1; i >= 0; i--) {
			siftDown(i);
		}
	}
	
	/**
	 * 上滤操作
	 * @param index
	 */
	private void siftUp(int index) {
		E element = elements[index];
		while (index > 0) {
			int parentIndex = (index - 1) >> 1;
			E parent = elements[parentIndex];
			if (compare(element, parent) <= 0) break;
			elements[index] = parent;
			index = parentIndex;
		}
		elements[index] = element;
	}
	
	/**
	 * 下滤操作
	 * @param index
	 */
	private void siftDown(int index) {
		E element = elements[index];
		int half = size >> 1;	// 非叶子节点数量(第一个叶子节点的索引)
		while (index < half) {
			int childIndex = (index << 1) + 1;
			E child = elements[childIndex];
			
			int rightIndex = childIndex + 1;
			if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
				child = elements[childIndex = rightIndex];
			}
			
			if (compare(element, child) >= 0) break;
			elements[index] = child;
			index = childIndex;
		}
		elements[index] = element;
	}
	
	private int compare(E e1, E e2) {
		if (comparator != null) return comparator.compare(e1, e2);
		return ((Comparable)e1).compareTo(e2);
	}
	
	private void ensureCapacity(int capacity) {
		int oldCapacity = elements.length;
		if (oldCapacity >= capacity) return;
		E[] newElements = (E[]) new Object[oldCapacity + (oldCapacity >> 1)];
		for (int i = 0; i < size; i++) {
			newElements[i] = elements[i];
		}
		elements = newElements;
	}
	
	private void emptyCheck() {
		if (size == 0) throw new IndexOutOfBoundsException("Heap is empty");
	}
	
	private void elementNotNullCheck(E element) {
		if (element == null) throw new NullPointerException("Element must not be null");
	}

}
